package LeetCode;

import java.util.ArrayList;

import LeetCode.BinaryTreeInorderTraversal.TreeNode;

public class BTMaxPathSum
{
  public static int maxPathSum(TreeNode root)
  {
    // pass the curmanx in an array that contains only one value
    ArrayList<Integer> curMax = new ArrayList<Integer>(1);
    curMax.add(Integer.MIN_VALUE);
    maxSubPath(root, curMax);
    return curMax.get(0);
  }

  private static int maxSubPath(TreeNode root, ArrayList<Integer> curMax)
  {
    if (root == null) return 0;
    int leftMax = Math.max(0, maxSubPath(root.left, curMax));
    int rightMax = Math.max(0, maxSubPath(root.right, curMax));
    curMax.set(0, Math.max(curMax.get(0), root.val + leftMax + rightMax));
    return Math.max(root.val + leftMax, root.val + rightMax);
  }

  /**
   * @param args
   */
  public static void main(String[] args)
  {
    // TODO Auto-generated method stub

  }

}
